/*
 * @lc app=leetcode.cn id=64 lang=cpp
 *
 * [64] 最小路径和
 *
 * https://leetcode.cn/problems/minimum-path-sum/description/
 *
 * algorithms
 * Medium (70.39%)
 * Likes:    1683
 * Dislikes: 0
 * Total Accepted:    607.3K
 * Total Submissions: 862.6K
 * Testcase Example:  '[[1,3,1],[1,5,1],[4,2,1]]'
 *
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 *
 *
 * 示例 2：
 *
 *
 * 输入：grid = [[1,2,3],[4,5,6]]
 * 输出：12
 *
 *
 *
 *
 * 提示：
 *
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 200
 * 0 <= grid[i][j] <= 200
 *
 *
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0x3f3f3f3f));
        dp[0][0] = grid[0][0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]);
                if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
        return dp[n - 1][m - 1];
    }
};
// @lc code=end

// 进阶输出路径（多个路径输出任意一条）
// class Solution {
// public:
//     int minPathSum(vector<vector<int>>& grid) {
//         int n = grid.size(), m = grid[0].size();
//         vector<vector<int>> dp(n, vector<int>(m, 0x3f3f3f3f));

//         // 0 代表从向下移动，1代表向右移动
//         vector<vector<int>> pre(n, vector<int>(m, 0));

//         dp[0][0] = grid[0][0];
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 if (i > 0 && dp[i - 1][j] + grid[i][j] < dp[i][j]) {
//                     dp[i][j] = dp[i - 1][j] + grid[i][j];
//                     pre[i][j] = 0;
//                 }
//                 if (j > 0 && dp[i][j - 1] + grid[i][j] < dp[i][j]) {
//                     dp[i][j] = dp[i][j - 1] + grid[i][j];
//                     pre[i][j] = 1;
//                 };
//             }
//         }
//         cout<<1<<endl;
//         printPath(pre);
//         return dp[n - 1][m - 1];
//     }
//     vector<pair<int, int>> printPath(vector<vector<int>> pre) {
//         int x = pre.size() - 1, y = pre[0].size() - 1, idx = x + y + 1;
//         vector<pair<int, int>> res(idx);
//         cout<<"print"<<endl;
//         while (--idx >= 0) {
//             res[idx] = {x, y};
//             cout << x << "," << y << endl;
//             if (pre[x][y])
//                 y--;
//             else
//                 x--;
//         }
//         return res;
//     }
// };

// int main(int argc, const char** argv) {
//     Solution solution = Solution();
//     vector<vector<int>> in = {{1,3,1}, {1,1,5}, {4,2,1}};
//     solution.minPathSum(in);
//     return 0;
// }